package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/print-binary-tree/">输出二叉树(Print Binary Tree)</a>
 * <p>给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：</p>
 * <ul>
 *     <li>树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。</li>
 *     <li>矩阵的列数 n 应该等于 2^(height+1) - 1 。</li>
 *     <li>根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。</li>
 *     <li>对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2^(height-r-1)] ，右子节点放置在 res[r+1][c+2^(height-r-1)] 。</li>
 *     <li>继续这一过程，直到树中的所有节点都妥善放置。</li>
 *     <li>任意空单元格都应该包含空字符串 "" 。</li>
 * </ul>
 * 返回构造得到的矩阵 res 。
 * <pre>
 * 示例 1：
 *      输入：root = [1,2]
 *                  1
 *                 /
 *                2
 *      输出：
 *          [["","1",""],
 *          ["2","",""]]
 *
 * 示例 2：
 *      输入：root = [1,2,3,null,4]
 *                  1
 *                 / \
 *                2   3
 *                 \
 *                  4
 *      输出：
 *          [["","","","1","","",""],
 *          ["","2","","","","3",""],
 *          ["","","4","","","",""]]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数在范围 [1, 2^10] 内</li>
 *     <li>-99 <= Node.val <= 99</li>
 *     <li>树的深度在范围 [1, 10] 内</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/24 10:47
 */
public class LC0655PrintTree_M {
    int height = 0;

    public List<List<String>> printTree(TreeNode root) {
        getMaxHeight(root, 0);
        int row = height + 1;
        int col = (int) (Math.pow(2, height + 1) - 1);
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            List<String> tempList = new ArrayList<>();
            for (int j = 0; j < col; j++) {
                tempList.add("");
            }
            res.add(tempList);
        }
        fillVal(root, 0, (col - 1) >> 1, res);
        return res;
    }

    public void fillVal(TreeNode root, int row, int col, List<List<String>> res) {
        if (root == null) {
            return;
        }
        res.get(row).set(col, String.valueOf(root.val));
        fillVal(root.left, row + 1, col - (int) Math.pow(2, height - row - 1), res);
        fillVal(root.right, row + 1, col + (int) Math.pow(2, height - row - 1), res);
    }

    private void getMaxHeight(TreeNode root, int currLevel) {
        if (root == null) {
            return;
        }
        if (currLevel > height) {
            height = currLevel;
        }
        getMaxHeight(root.left, currLevel + 1);
        getMaxHeight(root.right, currLevel + 1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(5);
        root.left.right.right = new TreeNode(6);
        root.right = new TreeNode(3);
        //LC0655PrintTree_M lc0655PrintTree_m = new LC0655PrintTree_M();
        //List<List<String>> lists = lc0655PrintTree_m.printTree(root);
        TreeNode.printTree(root);
    }
}
